package com.algrithom.bfs;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * 505. 迷宫 II 499. 迷宫 III
 * 
 * @author think
 */
public class Solution3 {
    
    private static final int[][] dirs = {{0,1},{0,-1},{-1,0},{1,0}};
    
    private static final String[] dirsStr = {"u","d","l","r"};
    
    public static void main(String[] args){
        int[][] maze = new int[][]{{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}};
        Solution3 solution3 = new Solution3();
        System.out.println(solution3.shortestDistance(maze,new int[]{0,4},new int[]{4,4}));
    }
    
    public int shortestDistance(int[][] maze,int[] start,int[] dest){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(start);
        
        int[][] mindiss = new int[maze.length][maze[0].length];
        for (int[] mindis : mindiss) {
            Arrays.fill(mindis,Integer.MAX_VALUE);
        }
        mindiss[start[0]][start[1]] = 0;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] dir : dirs) {
                int nextX = cur[0] + dir[0];
                int nextY = cur[1] + dir[1];
                int step = mindiss[cur[0]][cur[1]];
                
                /* loop for all valid moves */
                while (nextX >= 0 && nextX < maze.length && nextY >= 0 && nextY < maze[0].length && maze[nextX][nextY] == 0) {
                    nextX += dir[0];
                    nextY += dir[1];
                    step++;
                }
                nextX -= dir[0];
                nextY -= dir[1];
                if (step < mindiss[nextX][nextY]) {
                    mindiss[nextX][nextY] = step;
                    queue.add(new int[]{nextX,nextY});
                }
            }
        }
        if (mindiss[dest[0]][dest[1]] == Integer.MAX_VALUE) {
            return -1;
        }
        return mindiss[dest[0]][dest[1]];
    }
    
    public String findShortestWay(int[][] maze,int[] ball,int[] hole){
        
        return "";
    }
    
    private void dfs(int[][] maze,int[] cur,int[] end,Map<Integer,List<String>> map,int step,String str){
        int rowLen = maze.length;
        int colLen = maze[0].length;
        for (int i = 0; i < 4; i++) {
            int nextX = cur[0] + dirs[i][0];
            int nextY = cur[1] + dirs[i][1];
            str = str + dirsStr[i];
            while (nextX >= 0 && nextX < rowLen && nextY >= 0 && nextY < colLen && maze[nextX][nextY] == 0) {
                nextX = nextX + dirs[i][0];
                nextY = nextY + dirs[i][1];
                step++;
            }
            nextX = nextX - dirs[i][0];
            nextY = nextY - dirs[i][1];
            dfs(maze,new int[]{nextX,nextY},end,map,step + 1,str);
            str = str.substring(0,str.length() - 1);
        }
    }
}